/*Copyright (C) 2013-2021 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define N 200010
#define M 200010
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int n,m,s,tot=0,nbs[N],dis[N],heap_size,str[N],ptr[N],ans[N];
bool b[N];
struct Edge{
	int ed;
	int v;
	int next;
} edge[M];
void init(){
	int u,v,w;
	scanf("%d%d%d",&n,&m,&s);
	heap_size=n;
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&u,&v,&w);
		edge[++tot].ed=v;
		edge[tot].v=w;
		edge[tot].next=nbs[u];
		nbs[u]=tot;
	}
}
void pop(){
	int son,father=1;
	str[ptr[heap_size]]=1;
	ptr[1]=ptr[heap_size];
	dis[1]=dis[heap_size--];
	while(father*2<=heap_size){
		son=father*2;
		if(son<heap_size&&dis[son+1]<dis[son])son++;
		if(dis[father]<=dis[son])break;
		swap(str[ptr[son]],str[ptr[father]]);
		swap(ptr[son],ptr[father]);
		swap(dis[son],dis[father]);
		father=son;
	} 
}
void up(int son){
	int father;
	while(son>1) {
		father=son>>1;
		if(dis[son]<=dis[father]) {
			swap(str[ptr[son]],str[ptr[father]]);
			swap(ptr[son],ptr[father]);
			swap(dis[son],dis[father]);
		} else break;
		son=father;
	}
}
void DEBUG(){
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++)cout<<ptr[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++)cout<<str[i]<<" ";cout<<endl;
}
void Dijkstra(){
	for(int i=0;i<=n;i++){
		dis[i]=INF;
		str[i]=ptr[i]=i;
	}
	dis[1]=0;
	str[s]=1;
	ptr[1]=s;
	str[1]=s;
	ptr[s]=1;
	for(int i=1;i<=n;i++){
		int k=ptr[1];
		ans[k]=dis[1];
		pop();
//		DEBUG();
		b[k]=1;
		int j=nbs[k];
		while(j!=0){
			if(!b[edge[j].ed]&&ans[k]+edge[j].v<dis[str[edge[j].ed]]){
				dis[str[edge[j].ed]]=ans[k]+edge[j].v;
				up(str[edge[j].ed]);
			}
			j=edge[j].next;
		}
	}
}
int main() {
	init();
	Dijkstra();
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}
